//
//  main.c
//  冒泡+选择  sort
//
//  Created by Song on 2018/4/2.
//  Copyright © 2018年 Song. All rights reserved.
//

#include <stdio.h>

#define length  6
#define length2  9

// 冒泡（未优化）
void maopao() {
    int a[length] = {3,5,4,6,1,2};
    int i,j,temp;
    
    for (i = 0; i < length ; i++) {
        for (j = i+1; j<length; j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        printf("%d = ",a[i]);
    }
//    for (int b = 0; b < length; b++) {
//        printf("%d - ",a[b]);
//    }
}

// 优化后的冒泡
void maopao2() { // 冒泡排序的优化
//    int a[length2] = {3,5,4,6,1,2,9,8,7};
    int a[length2] = {2,1,3,4,5,6,7,8,9};
    int i,j,temp;
    
    int flag = 1; // 冒泡的优化（C语言没有bool类型，用flag代替）
    
    for (i = 0; i < length2 && flag == 1; i++) {
        
        flag = 0;
        
        for (j = length2-2 ; j >= i; j--) { // 从后向前，j = length - 2，且 j >= i
            if (a[j] > a[j+1]) {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                
                flag = 1;
            }
        }
        printf("%d = ",a[i]);
    }
    printf("\n");
    for (int b = 0; b < length2; b++) {
        printf("%d - ",a[b]);
    }
}

// 简单选择排序
void xuanze() {
//    int a[length2] = {2,1,3,4,5,6,7,8,9};
    int a[length2] = {3,5,4,6,1,2,9,8,7};
    int i,j,temp,min;
    
    for (i = 0; i<length2; i++) {
        min = i;
        for (j = i+1; j<length2; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        if (i != min) {
            printf("min: %d\n",min);
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
    for (int b = 0; b < length2; b++) {
        printf("%d - ",a[b]);
    }
}

int main(int argc, const char * argv[]) {
    
    maopao();
    printf("\n");
    maopao2();
    printf("\n");
    xuanze();
    
    printf("\n");
    return 0;
}
